import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        int[] nums = new int[]{};
        // System.out.println(test.findPeakElement(nums));

        // System.out.println(test.findMin(nums));

        System.out.println(test.takeAttendance(nums));
    }

    public int findPeakElement(int[] nums) {
        /**
         * 寻找峰值
         * 使用普通双指针解法
         * */
        // 1 预处理
        int n = nums.length;
        if(n == 1) return 0;

        // 2 双指针
        long left = 0;
        long right = n - 1;
        while(left < right) {
            int mid = (int)(left + (right - left) / 2);
            if(nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        // 3 返回值
        return (int)left;
    }

    public int findMin(int[] nums) {
        /**
         * 寻找旋转排列数组中的最小值*/
        // 1 预处理
        int n = nums.length;
        // -重要的一步，去除其为升序的可能，以简化后续操作
        if(nums[0] < nums[n-1]) return nums[0];

        // 2 二分查找（不管什么左边界右边界，反正直接干！）
        int left = 0;
        int right = n-1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[n-1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }

    public int takeAttendance(int[] records) {
        /**
         * 点名
         * */
        // 1 预处理
        int n = records.length;

        // 2 双指针
        int left = 0;
        int right = n-1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(mid == records[mid]) {
                // -若是相等，则缺失值必定不会在这及其之前，故left = mid+1
                left = mid + 1;
            } else {
                // -若是不相等，缺失值可能在这或者之前，故right = mid
                right = mid;
            }
        }
        // 3 返回值
        if(left == n-1 && records[left] == left) {
            // -出循环后，若是相交于n-1，其有两种情况，可能缺失n-1，可能缺失n，因此我们需要进行特判
            return left + 1;
        } else {
            return left;
        }
    }
}
